package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/15 14:01
 * @description：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
 */
public class 查找和最小的K对数字 {

    @Test
    public void test() {
        Solution solution = new Solution();
        List<List<Integer>> list = solution.kSmallestPairs(new int[]{1, 3, 10}, new int[]{2, 4, 6}, 6);
        list.forEach(System.out::println);
    }

    class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums2.length == 1 || nums1.length == 1) {
                int[] oneLenNums = nums1.length == 1 ? nums1 : nums2;
                int[] otherNums = nums1.length == 1 ? nums2 : nums1;
                for (int i = 0; i < k; i++) {
                    ans.add(Arrays.asList(otherNums[i], oneLenNums[0]));
                }
                return ans;
            }
            int i = 0, j = 0, prejj = 0;
            while (ans.size() < k) {
                int tar = 0;
                int jj = 0;
                while (jj + ans.size() < k && jj != nums2.length - 1) {
                    tar = nums1[i + 1] + nums2[j];
                    jj = binarySearch(nums2, tar);
                    j++;
                }
                for (int cur = prejj; cur < jj && ans.size() < k; cur++) {
                    ans.add(Arrays.asList(nums1[i], nums2[cur]));
                }
                prejj = jj;
                if (jj == nums2.length - 1) {
                    prejj = 0;
                    i++;
                }
            }
            return ans;
        }

        private int binarySearch(int[] nums, int t) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return nums[l] <= t ? l : -1;
        }
    }
}

